Search results for "Extremal graph theory"

showing 2 items of 2 documents

New results for finding common neighborhoods in massive graphs in the data stream model

2008

AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. Our results correct and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding common neighborhoods in massive graphs, Theoretical Computer Science, 299 (1–3) 707–718 (2004)]

Data streamDiscrete mathematicsGeneral Computer ScienceExtremal graph theorySpace lower boundsModel of computationCommunication complexityGraph theoryUpper and lower boundsTheoretical Computer ScienceExtremal graph theoryCombinatoricsGraph algorithms for data streamsAlgorithms Theoretical Computer SciencedGraph algorithmsCommunication complexityComputer Science(all)MathematicsTheoretical Computer Science
researchProduct

Counterexamples to the Algebraic Closed Graph Theorem

1982

Discrete mathematicssymbols.namesakeAlgebraic graph theoryGeneral MathematicsPerfect graphsymbolsGraph minorPerfect graph theoremClosed graph theoremRobertson–Seymour theoremPlanar graphMathematicsExtremal graph theoryJournal of the London Mathematical Society
researchProduct